package com.java.comprehensive.arithmetic.leecode.tags.array;

import java.util.Arrays;

/**
 * @program: comprehensive-service
 *
 * @description: 最接近的三数之和
 *
 * @author: 窦绍飞
 *
 * @create: 2021-12-08 15:09
 **/
public class LeetCode_16 {
	public static int threeSumClosest(int[] nums, int target) {

		Arrays.sort(nums);
		int n = nums.length;
		int temp = 1000000;
		for (int i = 0; i < n; i++) {
			if (i > 0 && nums[i] == nums[i - 1]) {
				continue;
			}
			int l = i + 1, r = n - 1;
			while (l < r) {
				int abs = nums[i] + nums[r] + nums[l];
				if (target == abs) {
					return abs;
				}

				if (Math.abs(abs - target) < Math.abs(temp - target)) {
					temp = abs;
				}
				if (abs > target) {
					int k0 = r - 1;
					while (l < k0 && nums[k0] == nums[r]) {
						--k0;
					}
					r = k0;
				} else {
					int j0 = l + 1;
					while (j0 < r && nums[j0] == nums[l]) {
						++j0;
					}
					l = j0;
				}

			}
		}

		return temp;
	}
	

	public static int threeSumClosestTwo(int[] nums, int target) {
		Arrays.sort(nums);
		int n = nums.length;
		int result = Integer.MAX_VALUE;
		for (int i = 0; i < n; i++) {
			if (i > 0 && nums[i] == nums[i - 1]) {
				continue;
			}
			int l = i + 1;
			int r = n - 1;
			while (l < r) {
				int abs = nums[i] + nums[l] + nums[r];
				if (abs == target)
					return abs;
				if (Math.abs(abs - target) < Math.abs(result - target)) {
					result = abs;
				}
				if (abs > target) {
					int k = r - 1;
					while (l < k && nums[r] == nums[k]) {
						--k;
					}
					r = k;
				} else {
					int k = l + 1;
					while (k < r && nums[k] == nums[l]) {
						++k;
					}
					l = k;
				}

			}

		}

		return result;
	}


	public static void main(String[] args) {
		int[] nums = { -1, 2, 1, -4 };
		int target = 1;
		int i = threeSumClosestTwo(nums, target);
		System.out.println(i);
	}
}
